/* 计算二叉树的深度 */
#include <iostream>
#include "BiTreefun.h"
using namespace std;

// 计算二叉树的深度 -- 方法一
int getDepth(BTNode *p)
{
  int LD, RD;
  
  // 二叉树为空
  if (p == NULL)
    return 0; // 深度为0
  
  // 二叉树不为空
  else
  {
    // 计算左子树的深度
    LD = getDepth(p->lchild);
    
    // 计算右子树的深度
    RD = getDepth(p->rchild);
    
    // 返回该二叉树的深度
    return (LD > RD ? LD : RD) + 1;
  }
}

// 计算二叉树的深度 -- 方法二
void getDepth2(BTNode *p, int &n, int &max)
{
  // 二叉树不为空
  if (p != NULL)
  {
    ++n; // n记录着当前根结点的所处深度
    
    // max记录最大深度
    if (n >= max)
      max = n;
    
    // 计算左子树的深度
    getDepth2(p->lchild, n, max);
    
    // 计算右子树的深度
    getDepth2(p->rchild, n, max);
    --n;
  }
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  int n = 0, max = 1;
  
  // 计算二叉树的深度
  getDepth2(T, n, max);
  cout << "二叉树的深度为:" << max << endl;
}